#pragma once
#include <string>
#include <stack>
#include <queue>
using namespace std;

class Parser
{
private:

	//constant
	string action_column[8] = {
    	"(",
    	")",
    	"+",
    	"-",
    	"*",
    	"/",
    	"num",
    	"$",
	};

	string action_table[30][8] = {
		{"S4","","","","","","S5",""},             //0
		{"","","S6","S7","","","","ACC"},          //1
		{"","","R3","R3","S8","S9","","R3"},       //2
		{"","","R6","R6","R6","R6","","R6"},       //3
		{"S13","","","","","","S14",""},           //4
		{"","","R8","R8","R8","R8","","R8"},       //5
		{"S4","","","","","","S5",""},             //6
		{"S4","","","","","","S5",""},             //7
		{"S4","","","","","","S5",""},             //8
		{"S4","","","","","","S5",""},             //9
		{"","S19","S20","S21","","","",""},        //10
		{"","R3","R3","R3","S22","S23","",""},     //11
		{"","R6","R6","R6","R6","R6","",""},       //12
		{"S13","","","","","","S14",""},           //13
		{"","R8","R8","R8","R8","R8","",""},       //14
		{"","","R1","R1","S8","S9","","R1"},       //15
		{"","","R2","R2","S8","S9","","R2"},       //16
		{"","","R4","R4","R4","R4","","R4"},       //17
		{"","","R5","R5","R5","R5","","R5"},       //18
		{"","","R7","R7","R7","R7","","R7"},       //19
		{"S13","","","","","","S14",""},           //20
		{"S13","","","","","","S14",""},           //21
		{"S13","","","","","","S14",""},           //22
		{"S13","","","","","","S14",""},           //23
		{"","S28","S20","S21","","","",""},        //24
		{"","R1","R1","R1","S22","S23","",""},     //25
		{"","R4","R4","R4","R4","R4","",""},       //26
		{"","R5","R5","R5","R5","R5","",""},       //27
		{"","R7","R7","R7","R7","R7","",""},       //28
		{"","R2","R2","R2","S22","S23","",""}      //29
	};    

	int goto_table[30][3] = {
			{1,2,3},       //0
			{-1,-1,-1},    //1
			{-1,-1,-1},    //2
			{-1,-1,-1},    //3
			{10,11,12},    //4
			{-1,-1,-1},    //5
			{-1,15,3},     //6
			{-1,16,3},     //7
			{-1,-1,17},    //8
			{-1,-1,18},    //9
			{-1,-1,-1},    //10
			{-1,-1,-1},    //11
			{-1,-1,-1},    //12
			{24,11,12},    //13
			{-1,-1,-1},    //14
			{-1,-1,-1},    //15
			{-1,-1,-1},    //16
			{-1,-1,-1},    //17
			{-1,-1,-1},    //18
			{-1,-1,-1},    //19
			{-1,25,12},    //20
			{-1,29,12},    //21
			{-1,-1,26},    //22
			{-1,-1,27},    //23
			{-1,-1,-1},    //24
			{-1,-1,-1},    //25
			{-1,-1,-1},    //26
			{-1,-1,-1},    //27
			{-1,-1,-1},    //28
			{-1,-1,-1}     //29
	};

	string expression[9] = {
    	"",
    	"E->E+T",
    	"E->E-T",
    	"E->T",
    	"T->T*F",
    	"T->T/F",
    	"T->F",
    	"F->(E)",
    	"F->num",
	};

	//步骤
	int step;
	//状态表
	stack<int> state;
	//符号表
	stack<string> symbol;
	//字符序列
	queue<string> letters;

private:
	//规约
	bool reduce(string action);
	//移进
	bool shift(string action);
	//打印这一行
	void printLine(string action);
	//打印栈和队列
	template <typename T> void printStack(stack<T> s);
	void printQueue(queue<string> q);
	//查找action表的列
	int index(string str);
	//错误处理
	void error();

public:
	//语法分析程序入口
	bool parse();

	Parser();
	Parser(string input);
};
